package tree;

import apple.laf.JRSUIUtils;

import javax.sound.midi.Soundbank;
import java.util.LinkedList;

public class MaxWidthOfTree662 {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    public static int widthOfBinaryTree(TreeNode root) {
        LinkedList<TreeNode> q = new LinkedList<>();
        int max = 0;
        int count = 0;
        int endSignal = 0;
        TreeNode end = null;
        TreeNode nextEnd = null;
        boolean startValid = false;
        q.add(root);
        end = root;
        while (q.size() != 0) {
            TreeNode head = q.poll();

            if (head != null) {
                startValid = true;

            } else {
                TreeNode empty = new TreeNode(-1);
                head = empty;
            }
            //we add the left and right child into the q no matter they are null or not
            q.add(head.left);
            if (head.left != null)
                nextEnd = head.left;
            q.add(head.right);
            if (head.right != null)
                nextEnd = head.right;

            if (startValid)
                count++;

            if (end == nextEnd) {
                endSignal++;
            }
            if (head == end) {
                max = Math.max(count, max);
                count = 0;
                end = nextEnd;
                startValid = false;
                endSignal = 0;
            }
            //if all member in the q is null, we know we have reached the end
//            int null_no = 0;
//            for(TreeNode n: q){
//                if(n ==  null)
//                    null_no++;
//            }
//            if(q.size() == null_no)
//                break;

            if (endSignal > 2 * max)
                break;
        }
        return max;
    }


    public static void main(String[] args) {

        TreeNode root = new TreeNode(1);
        TreeNode cur = root;
        for (int i = 0; i < 3; i++) {
            cur.left = new TreeNode(1);
            cur = cur.left;
        }
        cur = root;
        for (int i = 0; i < 3; i++) {
            cur.right = new TreeNode(1);
            cur = cur.right;
        }
        System.out.println(widthOfBinaryTree(root));
        System.out.println("Correct answer is 8");
    }
}
